#ifndef ___HASHTABLE___
#define ___HASHTABLE___

#include <stdlib.h>

#define EMP 0
#define STR -1
#define NUM -2
#define FUN -3

typedef struct _HTVAL
{
	char t;
	int l;
	int al;
	long n;
	char* s;
	void* f;
} HTVAL;

typedef	struct _HTKEY
{
	char t;
	long i;
	char* s;
}HTKEY;

typedef struct _DATA{

	HTKEY key;
	HTVAL val;

	_DATA* next;
} HTDATA;

class HashTable
{

	
	HTDATA * data;

	HTDATA * Ptr,* PrePtr;
	
	unsigned int SearchIdx;
	unsigned int TBL_SIZE;
	
	int hash(const char* k)
	{
		int h = 0;
		if (!k) { return 0; }
		while (*k != 0) {
			h = (h * 7) ^ *k;
			++k;
		}
		if (h < 0) { h = -h; }
		return h;
	}

	int StrLen(const char* s)
	{
		int i = 0;
		if (s)
			while(*s++) i++;
		return i;
	}

	char* MemCpy(char* dst, const char* src, int n)
	{
		if (!dst) return 0;
		char* ret = dst;
		if (!src || n<=0)
		{
			while (n-->0)
				*dst++ = '\0';
			return ret;
		}
		while(n-->0)
			*dst++ = *src++;
		*dst=0;
		return ret;
	}

	char* MemDup(const char* src, int n=0)
	{
		if (!n) 
		{
			if (src)
				n = StrLen(src);
			else
				return 0;
		}
		char* ret,*dst;
		ret = dst = (char*)malloc(n*sizeof(char)+1);
		if (src)
		{
			while(n--)
				*dst++ = *src++;
			*dst = 0;
		}
		return ret;
	}

	bool MemCmp(char* s,char* d,int n=0)
	{
		if (!d || !s) return false;
		if (!n)n=StrLen(s);
		while(n--)
		{
			if (*d++ != *s++) return false;
		}
		return true;
	}

	void ZeroMem(void* d,int l)
	{
		while(l--)
		{
                *(char *)d = 0;
                d = (char *)d + 1;
        }
	}

	void ClearVal(HTDATA* p)
	{
		if (p->val.s)
		{
			free(p->val.s);
			p->val.s = 0;
		}
		p->val.al = p->val.l = 0;
		if (p->val.f) p->val.f = 0;
		p->val.n = 0;
		p->val.t = EMP;
	}

	void ClearKey(HTDATA* p)
	{
		if (p->key.s)
		{
			free(p->key.s);
			p->key.s = 0;
		}
		p->key.i = 0;
		p->key.t = EMP;
	}

public:	

	HashTable(int size=128)	{ data=NULL;Init(size);}
	~HashTable()
	{
		for(unsigned int i=0;i<TBL_SIZE;i++)
		{
			Ptr = &data[i];
			do 
			{
				if (Ptr->val.s)
					free(Ptr->val.s);
				if (Ptr->key.s)
					free(Ptr->key.s);
				Ptr=Ptr->next;
			} while (Ptr);
		}
	}

	void Init(int size)
	{
		TBL_SIZE = size;
		if (data) free(data);
		data = new HTDATA[size]; 
		PrePtr = Ptr = data;
		ZeroMem(data,size*sizeof(HTDATA));
	}

	void Set(char *k, long v)
	{
		int tp = GetValueType(k);
		if (tp==EMP) 
		{
			Ptr->key.s = MemDup(k);
		}
		Ptr->key.t = STR;
		Ptr->val.n = (long)v;
		Ptr->val.t = NUM;
	}

	void Set(char *k, char* s,int n=0)
	{
		int tp = GetValueType(k);
		if (!n)n = StrLen(s);
		if (tp==EMP) 
			Ptr->key.s = MemDup(k);
		Ptr->key.t = STR;
		if (Ptr->val.s)
		{
			if (n>=Ptr->val.al) 
			{
				Ptr->val.s = (char*)realloc(Ptr->val.s,n+1);
				Ptr->val.al=n+1;
			}
			MemCpy(Ptr->val.s,s,n);
		}
		else
		{
			Ptr->val.s = MemDup(s,n);
			Ptr->val.al = n+1;
		}
		Ptr->val.l = n;
		Ptr->val.t = STR;
	}

	void Set(long k, long v)
	{
		int tp = GetValueType(k);
		
		Ptr->key.i = k;
		Ptr->key.t = NUM;
		Ptr->val.n = v;
		Ptr->val.t = NUM;
	}

	void Set(long k, char* s, int n=0)
	{
		int tp = GetValueType(k);
		if (!n)n = StrLen(s);

		Ptr->key.i = k;
		Ptr->key.t = NUM;
		if (Ptr->val.s)
		{
			if (n>=Ptr->val.al) 
			{
				Ptr->val.s = (char*)realloc(Ptr->val.s,n+1);
				Ptr->val.al=n+1;
			}
			MemCpy(Ptr->val.s,s,n);
		}
		else
		{
			Ptr->val.s = MemDup(s,n);
			Ptr->val.al = n+1;
		}
		Ptr->val.l = n;
		Ptr->val.t = STR;
	}

	void Set(char* k, void* f)
	{
		int tp = GetValueType(k);
		if (tp==EMP) Ptr->key.s = MemDup(k);
		Ptr->key.t = STR;
		Ptr->val.f = f;
		Ptr->val.t = FUN;
	}

	HTVAL* Get(char* k)
	{
		return Get(hash(k),k);
	}

	HTVAL* Get(long k, char* s=0)
	{
		GetValueType(k,s);

		if (Ptr) return &Ptr->val;
		return NULL;
	}

	int GetValueType(char *k)
	{
		int i = hash(k);
		return GetValueType(i,k);
	}

	int GetValueType(long k,char* s=0)
	{
		long l=k;
		int i = k % TBL_SIZE;
		int b = k / TBL_SIZE;
		HTDATA* o = PrePtr = Ptr = &data[i];
		if (o)
		{
			if (o->val.t==EMP) return EMP;
			do
			{
				if (o->key.t==STR)
				{
					if (s && o->key.s && MemCmp(o->key.s,s)) 
					{
						Ptr = o;
						return o->val.t;
					}
				}
				else
				{
					if (o->key.i==l)
					{
						Ptr = o;
						return o->val.t;
					}
				}
				PrePtr = o;
				o = o->next;
			}
			while (o);

			Ptr->next = new HTDATA;
			Ptr = Ptr->next;
			ZeroMem(Ptr,sizeof(HTDATA));
		}
		return EMP;
	}

	bool Remove(char* k)
	{
		return Remove(hash(k),k);
	}

	bool Remove(long k,char * s = 0)
	{
		int tp = GetValueType(k,s);
		if (tp!=EMP)
		{
			if (PrePtr==Ptr)
			{
				ClearVal(Ptr);
				ClearKey(Ptr);
				PrePtr->key.t = Ptr->next->key.t;
				PrePtr->key.i = Ptr->next->key.i;
				PrePtr->key.s = MemDup(Ptr->next->key.s);
				PrePtr->val.t = Ptr->next->val.t;
				PrePtr->val.n = Ptr->next->val.n;
				PrePtr->val.l = Ptr->next->val.l;
				PrePtr->val.al = Ptr->next->val.al;
				PrePtr->val.f = Ptr->next->val.f;
				PrePtr->val.s = MemDup(Ptr->next->val.s,Ptr->next->val.al);
				ClearVal(Ptr->next);
				ClearKey(Ptr->next);
				delete Ptr->next;
				Ptr->next = 0;
			}
			else
			{
				if (Ptr->next) 
					PrePtr->next = Ptr->next;
				else
					PrePtr->next = 0;
				ClearVal(Ptr);
				ClearKey(Ptr);
				delete Ptr;
				Ptr = 0;
			}
		}
		return true;
	}

	HTDATA* First()
	{
		Ptr = data;
		SearchIdx = 0;
		while (Ptr->val.t == EMP)
		{
			if (SearchIdx>=TBL_SIZE)
			{
				Ptr = PrePtr = NULL;
				return Ptr;
			}
			SearchIdx ++;
			Ptr++;
		}

		PrePtr = Ptr;
		return Ptr;
	}

	HTDATA* Next()
	{
		if (Ptr->next) 
		{
			Ptr = Ptr->next;
			return Ptr;
		}
		
		do
		{
			SearchIdx ++;
			PrePtr++;
			if (SearchIdx>=TBL_SIZE)
			{
				Ptr = PrePtr = NULL;
				return Ptr;
			}
		}while(PrePtr->val.t == EMP);
		Ptr = PrePtr;
		return Ptr;
	}

	HTKEY* GetKey()
	{
		return &Ptr->key;
	}

	HTVAL* GetValue()
	{
		return &Ptr->val;
	}
};

#endif

